This invention relates to the field of retrieval of information stored on digital information storage disks, and in particular to an apparatus and method for rapidly and efficiently locating user data stored on an information recording disk.
With information storage devices such as magnetic tape drives, the need for extensive indexing is minimal since the data is recorded, and must be read, sequentially. However, with the development of random access information storage disks, the need for indexing methods developed, in order to find specific blocks or user information. Also, as digital data has been ever more densely written on information recording disks, the need to provide a means for rapidly and efficiently searching and recovering specific user data has become even more difficult.
The early response to the problem was in the indexing of disk data. That is, providing a short hand means, which has been generally entitled a Key, whereby user data is given a designation which uniquely identifies the larger data grouping, thereby allowing a somewhat more efficient search of the index in order to find the specific data grouping sought. Indexing has generally involved either placing some unique identifier Key in the header portion of the user data and storing that identifier in a separate memory, or by taking some unique characteristic of the user data and making that value the Key. In magnetic disks, as the data is recorded and transferred to the host, an extensive Index, indicating the platter content and location of specific data blocks, is created for that disk. This was a partial solution to the problem of data storage and efficient retrieval. An early example of this method is the IBM Count Key system.
However, as data is written more densely on the disk surface, and since indexing has taken up ever more real estate on the platter surface the need for even more efficient disk indexing systems has become evident. Users have a continuing need to rapidly access the stored data. The more extensive the Index, the longer the search time necessary to find a specific set of user data. With the data being more densely written on the disk surface, this time has increased, with a corresponding decrease in the utility of the system.
Also, the need has developed for a user to be able to search a given data base for a specific set of data based upon more than one Key indexing method. To do this, a multiple Key system is necessary, in that if the data sought could be more efficiently searched based upon a "sort" other than the means by which it is initially indexed, the search would be less inefficient and time consuming. For example, if the data were sorted and indexed with regard to social security numbers, a search that could be efficiently done by address or by age would be most difficult. The present systems in use generally have a single identifier Key and sort for the indexing method.
In more recent years, there has also been increased development in recording devices having removeable media. This has intensified the need for an efficient means of indexing data recorded on the device surface, because to efficiently access the data recorded on the disk, the disk must carry its complete Index with it, and as storage devices move toward using single platters as opposed to disk packs, the need for an efficient indexing system has become critical.
Most importantly, as optical media having its write once only capability has been developed, the prior indexing and searching schemes have become inappropriate. In magnetic disk, with its erasable capability, data can be replaced and/or rather easily re-ordered. In particular, if data has a specific sequence and new data is presented which should be inserted therein, it is relatively easy to re-record the data placing the new entry in its appropriate place. Also, if a defect in the platter surface prevents the recording of data, the data can be recorded elsewhere and a pointer recorded leading to the new location, thus allowing the host to view the data as recorded on the platter location intended. These approaches are not possible with noneraseable media. Therefore, a new method of writing data, indexing and searching such data must be developed. What is needed therefore, for all information recording disks, is a more efficient means for indexing and searching for user data that does not also use up significant platter storage capacity. Also needed is a tool which would allow the user to efficiently access ever larger volumes of data on the platter surface based upon multiple sorting and indexing schemes, without a corresponding increase in the use of platter storage capacity for such indexing. Also needed is a system which would allow a "write once only" disk to be written upon, indexed, and searched, at least as efficiently as erasable media. And finally, a system is needed which can support an Index for a device having removeable media.